package Greedy;//老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
//
// 你需要按照以下要求，帮助老师给这些孩子分发糖果： 
//
// 
// 每个孩子至少分配到 1 个糖果。 
// 评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。 
// 
//
// 那么这样下来，老师至少需要准备多少颗糖果呢？ 
//
// 
//
// 示例 1： 
//
// 
//输入：[1,0,2]
//输出：5
//解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
// 
//
// 示例 2： 
//
// 
//输入：[1,2,2]
//输出：4
//解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
//     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。 
// Related Topics 贪心 数组 👍 703 👎 0


import java.util.Arrays;

//leetcode submit region begin(Prohibit modification and deletion)
class candy {
    /**
     分两个阶段
     1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1
     2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，
     此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大
     */
    public int candy(int[] ratings) {
        //题目要求评分高的要比相邻的多，且每个人至少一个

        int len = ratings.length;
        if(len==1){
            return 1;
        }
        int[] res = new int[len];
        res[0] = 1;
        //那么先进行左向右的遍历，右边的和左边进行比较，看单向的谁多，若右边的多，右边获得比左边数量+1的糖果。否则默认为1个，以保证每人至少一个和单向更多
        for(int i=1;i<len;i++){
            if(ratings[i] > ratings[i-1]){
                res[i] = res[i-1] + 1;
            }else{
                res[i] = 1;
            }
        }
        //再次从右向左遍历，看左边和右边的进行比较，如果左边的分数更多，此时如果左边的糖果已经多于右边了，不需要变，否则是右边的数量+1，因此取二者最大即可
        for(int i=len-2;i>=0;i--){
            if(ratings[i] > ratings[i+1]){
                res[i] = Math.max(res[i], res[i+1]+1);
            }
        }

        return Arrays.stream(res).sum();

    }
}
//leetcode submit region end(Prohibit modification and deletion)
